#include "InterviewStack.h"
#include "SeqQueue.h"
#include "SeqStack.h"
//****************判断两个字符串是否按照出栈顺序****************

int IsStackOrder(char input[],int64_t size_in,char output[],int64_t size_out)
{
    if(NULL==input||NULL==output||size_in<=0||size_out<=0)
    {
        return 0;
    }
    int64_t index_in=0;
    int64_t index_out=0;
    SeqStack stack;
    SeqStackType tmp='\0';
    SeqStackInit(&stack);

    while(index_in<size_in)
    {
        SeqStackPush(&stack ,input[index_in++]);
        if(SeqStackTop(&stack,&tmp)==0)
        {
            break;
        }
        while(SeqStackTop(&stack,&tmp)!=0)
        {
           if(tmp==output[index_out])
           {//如果当前的匹配的话
               SeqStackPop(&stack);//出栈
               index_out++;
            }
           else
           {
                break;
           }
       }
    }
//break出来的
    if(size_out==index_out&&SeqStackTop(&stack,&tmp)==0)
    {
        return 1;
    }
    else
    {
        printf("indexout:%ld,size_out:%ld\n",index_out,size_out);
        return 0;
    }
}


//*******************实现最小栈的方法一***************

//打印最小栈中的内容
void PrintMinStack(MinStack *minstack,const char *msg)
{
    if(NULL==minstack||NULL==msg)
    {
        return;
    }
    SeqStackPrintChar(&minstack->date,msg);
}
//最小栈的初始化
void MinStackInit(MinStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    SeqStackInit(&minstack->date);
    SeqStackInit(&minstack->min);
}
//最小栈的入栈操作
void MinStackPush(MinStack *minstack,MinStackType value)
{
    if(NULL==minstack)
    {
        return;
    }
    if(SeqStackSize<=minstack->date.size)
    {
        return;
    }
    MinStackType tmp;
   if(0== SeqStackTop(&minstack->min,&tmp))
   {
       SeqStackPush(&minstack->date,value);
       SeqStackPush(&minstack->min,value);
   }
   else
   {
       if(value>tmp)
       {
           SeqStackPush(&minstack->date,value);
           SeqStackPush(&minstack->min,tmp);
       }
       else
       {
          SeqStackPush(&minstack->date,value);
          SeqStackPush(&minstack->min,value);
       }
   }
}
//最小栈的出栈操作
void MinStackPop(MinStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    if(0==minstack->date.size)
    {
        return;
    }
    SeqStackPop(&minstack->date);
    SeqStackPop(&minstack->min);
}
//最小栈的取栈顶元素
int MinStackTop(MinStack *minstack ,MinStackType *tmp)
{
    if(NULL==minstack||NULL==tmp)
    {
        return 0;
    }
    MinStackType value;
    if(SeqStackTop(&minstack->min,&value)!=0)
    {
        *tmp=value;
        return 1;
    }
    else
    {
        return 0;
    }
}
//最小栈的销毁
void MinStackDestroy(MinStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    SeqStackDestroy(&minstack->date);
    SeqStackDestroy(&minstack->min);
}
//******************实现最小栈的方法二*******************
//打印最小栈
void PrintMinStack_1(SeqStack *minstack,const char *msg)
{
    if(NULL==minstack||NULL==msg)
    {
        return;
    }
    printf("\n%s\n",msg);
    size_t i=0;
    for(i=minstack->size;i>0;i=i-2)
    {
        printf("[%c] ",minstack->data[i-1]);
    }
    printf("\n");
}
//最小栈的初始化
void MinStackInit_1(SeqStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    SeqStackInit(minstack);
}
//最小栈的入栈
void  MinStackPush_1(SeqStack *minstack,MinStackType value)
{
    if(NULL==minstack)
    {
        return;
    }
    if(minstack->size>=SeqStackSize)
    {
        return;
    }
    SeqStackType tmp;
    if(SeqStackTop(minstack,&tmp)==0)
    {
        SeqStackPush(minstack,value);
        SeqStackPush(minstack,value);
    }
    else
    {
        if(value>tmp)
        {
            SeqStackPush(minstack,value);
            SeqStackPush(minstack,tmp);
        }
        else
        {
            SeqStackPush(minstack,value);
            SeqStackPush(minstack,value);
        }
    }
}
//最小栈的出栈操作
void MinStackPop_1(SeqStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    if(SeqStackGetSize(minstack)==0)
    {
        return;
    }
    SeqStackPop(minstack);
    SeqStackPop(minstack);
}
//最小栈的取栈顶元素
int MinStackTop_1(SeqStack *minstack,MinStackType *tmp)
{
    if(NULL==minstack||NULL==tmp)
    {
        return 0;
    }
    SeqStackType value;
    if(SeqStackTop(minstack,&value)!=0)
    {
        *tmp=value;
        return 1;
    }
    else
    {
        return 0;
    }
}
//最小栈的销毁
void MinStackDestroy_1(SeqStack *minstack)
{
    if(NULL==minstack)
    {
        return;
    }
    SeqStackDestroy(minstack);
}
//****************两个栈实现一个队列***********************
//打印队列的内容
void PrintQueue(Queue *queue,const char *msg)
{
    if(NULL==queue||NULL==msg)
    {
        return;
    }

    if(SeqStackGetSize(&queue->Spush)==0&&SeqStackGetSize(&queue->Spop)==0)
    {
        return;
    
    }
    SeqStackType tmp;
    while(SeqStackTop(&queue->Spop,&tmp)!=0)
    {
        SeqStackPop(&queue->Spop);
        SeqStackPush(&queue->Spush,tmp);
    }
    SeqStackPrintChar(&queue->Spush,msg);
}
//队列的初始化
void QueueInit(Queue *queue)
{
    if(NULL==queue)
    {
        return;
    }
    SeqStackInit(&queue->Spush);
    SeqStackInit(&queue->Spop);
}
//入队列操作
void QueuePush(Queue *queue,QueueType value)
{
    if(NULL==queue)
    {
        return;
    }
    if(queue->Spop.size>=SeqStackSize||queue->Spop.size>=SeqStackSize)
    {
        return;
    }
    SeqStackType tmp;
    if(SeqStackGetSize(&queue->Spush)==0&&SeqStackGetSize(&queue->Spop)==0)
    {
        SeqStackPush(&queue->Spush,value);
    }
    else
    {
        while(SeqStackTop(&queue->Spop,&tmp)!=0)
        {
            SeqStackPop(&queue->Spop);
            SeqStackPush(&queue->Spush,tmp);
        }
        SeqStackPush(&queue->Spush,value);
    }
}
//出队列操作
void QueuePop(Queue *queue)
{
    if(NULL==queue)
    {
        return;
    }
    if(SeqStackGetSize(&queue->Spush)==0&&SeqStackGetSize(&queue->Spop)==0)
    {
        return;
    }
    SeqStackType tmp;
    while(SeqStackTop(&queue->Spush,&tmp)!=0)
    {
        SeqStackPop(&queue->Spush);
        SeqStackPush(&queue->Spop,tmp);
    }
    SeqStackPop(&queue->Spop);
}
//取队首元素
int QueueFront(Queue *queue,QueueType *tmp)
{
    if(NULL==queue||NULL==tmp)
    {
        return 0;
    }
    if(SeqStackGetSize(&queue->Spush)==0&&SeqStackGetSize(&queue->Spop)==0)
    {
        return 0;
    }
    SeqStackType value;
    while(SeqStackTop(&queue->Spush,&value)!=0)
    {
        SeqStackPop(&queue->Spush);
        SeqStackPush(&queue->Spop,value);
    }
    if(SeqStackTop(&queue->Spop,&value)!=0)
    {
        *tmp=value;
        return 1;
    }
    else
    {
        return 0;
    }
}
//销毁一个队列
void QueueDestroy(Queue *queue)
{
    if(NULL==queue)
    {
        return;
    }
    SeqStackDestroy(&queue->Spush);
    SeqStackDestroy(&queue->Spop);
}
//*****************两个队列实现一个栈***************************
//打印栈中的内容
void PrintStack(Stack *stack,const char *msg)
{
    if(NULL==stack||NULL==msg)
    {
        return;
    }
    if(SeqQueueGetSize(&stack->q1)==0&&SeqQueueGetSize(&stack->q2)==0)
    {
        return;
    }
    if(SeqQueueGetSize(&stack->q1)==0)
    {
        SeqQueuePrintChar(&stack->q2,msg);
        return;
    }
    if(SeqQueueGetSize(&stack->q2)==0)
    {
        SeqQueuePrintChar(&stack->q1,msg);
    }

}
//栈的初始化
void StackInit(Stack *stack)
{
    if(NULL==stack)
    {
        return;
    }
    SeqQueueInit(&stack->q1);
    SeqQueueInit(&stack->q2);
}
//入栈操作
void StackPush(Stack *stack,StackType value)
{
    if(NULL==stack)
    {
        return;
    }
    if(stack->q1.size>=SeqQueueSize||stack->q2.size>=SeqQueueSize)
    {
        return;
    }
    if(SeqQueueGetSize(&stack->q2)==0)
    {
        SeqQueuePush(&stack->q1,value);
    }
    else
    {
        SeqQueuePush(&stack->q2,value);
    }
}
//出栈操作
void StackPop(Stack *stack)
{
    if(NULL==stack)
    {
        return;
    }
    if(SeqQueueGetSize(&stack->q1)==0&&SeqQueueGetSize(&stack->q2)==0)
    {
        return;
    }
    SeqQueueType tmp;
    if(SeqQueueGetSize(&stack->q1)==0)
       {
           while(SeqQueueGetSize(&stack->q2)>=2)
           {
               SeqQueueFront(&stack->q2,&tmp);
               SeqQueuePop(&stack->q2);
               SeqQueuePush(&stack->q1,tmp);
           }
            SeqQueuePop(&stack->q2);
            return;
       }
    if(SeqQueueGetSize(&stack->q2)==0)
       {
           while(SeqQueueGetSize(&stack->q1)>=2)
           {
               SeqQueueFront(&stack->q1,&tmp);
               SeqQueuePop(&stack->q1);
               SeqQueuePush(&stack->q2,tmp);
           }
            SeqQueuePop(&stack->q1);
       }
}
//取栈顶元素
int StackTop(Stack *stack,StackType *tmp)
{
    
    if(NULL==stack||NULL==tmp)
    {
        return 0;
    }
    if(SeqQueueGetSize(&stack->q1)==0&&SeqQueueGetSize(&stack->q2)==0)
    {
        return 0;
    }
    SeqQueueType value;
    if(SeqQueueGetSize(&stack->q1)==0)
       {
           while(SeqQueueGetSize(&stack->q2)>=1)
           {
               SeqQueueFront(&stack->q2,&value);
               SeqQueuePop(&stack->q2);
               SeqQueuePush(&stack->q1,value);
           }
           *tmp=value;
            return 1;
       }
    if(SeqQueueGetSize(&stack->q2)==0)
       {
           while(SeqQueueGetSize(&stack->q1)>=1)
           {
               SeqQueueFront(&stack->q1,&value);
               SeqQueuePop(&stack->q1);
               SeqQueuePush(&stack->q2,value);
           }
           *tmp=value;
           return 1;
       }
    return 0;
}
//销毁栈
void StackDestroy(Stack *stack)

{
    if(NULL==stack)
    {
        return;
    }
    SeqQueueDestroy(&stack->q1);
    SeqQueueDestroy(&stack->q2);
}
//打印栈一中的内容
void PrintShareStack_1(ShareStack *share,const char *msg)
{
    if(NULL==share)
    {
        return;
    }
    size_t i=0;
    printf("\n%s\n",msg);
    printf("栈顶： ");
    for(i=share->top1;i>0;i--)
    {
        printf("[%c] ",share->data[i-1]);
    }
    printf("\n");
}
//打印栈二中的内容
void PrintShareStack_2(ShareStack *share,const char *msg)
{
    if(NULL==share)
    {
        return;
    }
    size_t i=0;
    printf("\n%s\n",msg);
    printf("栈顶  ");
    for(i=share->top2;i<SeqStackSize-1;i++)
    {
        printf("[%c] ",share->data[i+1]);
    }
    printf("\n");
}
//共享栈的初始化
void ShareStackInit(ShareStack *share)
{
    if(NULL==share)
    {
        return;
    }
    share->top1=0;
    share->top2=SeqStackSize-1;
}
//栈一的入栈
void ShareStackPush_1(ShareStack *share,ShareStackType value)
{
    if(NULL==share)
    {
        return;
    }
    if(share->top1==share->top2)
    {
        return;
    }
    share->data[share->top1]=value;
    share->top1++;
}
//栈二的入栈
void ShareStackPush_2(ShareStack *share,ShareStackType value)
{
    if(NULL==share)
    {
        return;
    }
    if(share->top1==share->top2)
    {
        return;
    }
    share->data[share->top2]=value;
    share->top2--;
}
//栈一的出栈
void ShareStackPop_1(ShareStack *share)
{
    if(NULL==share)
    {
        return;
    }
    if(share->top1==0)
    {
        return;
    }
    share->top1--;
}
//栈二的出栈
void ShareStackPop_2(ShareStack *share)
{
    if(NULL==share)
    {
        return;
    }
    if(share->top2==SeqStackSize-1)
    {
        return;
    }
    share->top2++;
}
//取栈一栈顶元素
int ShareStackTop_1(ShareStack *share,ShareStackType *tmp)
{
    if(NULL==share||NULL==tmp)
    {
        return 0;
    }
    if(share->top1==0)
    {
        return 0;
    }
    *tmp=share->data[share->top1-1];
    return 1;
}
//取栈二的栈顶元素
int ShareStackTop_2(ShareStack *share,ShareStackType *tmp)
{
    if(NULL==share||NULL==tmp)
    {
        return 0;
    }
    if(share->top2==SeqStackSize-1)
    {
        return 0;
    }
    *tmp=share->data[share->top2+1];
    return 1;
}
//销毁栈一
void ShareStackDestroy_1(ShareStack *share)
{
    if(NULL==share)
    {
        return;
    }
    share->top1=0;
}
//销毁栈二
void ShareStackDestroy_2(ShareStack *share)
{
    if(NULL==share)
    {
        return;
    }
    share->top2=SeqStackSize-1;
}



